When running multiple applications in real time on avionics hardware in a partitioned environment (e.g., ARINC 653), each application is said to be partitioned by time, by space, and by resource. Time partitioning refers to the deterministic execution of an application. Given a particular set of inputs, the application will always produce the same set of outputs (ex.—results). Another interpretation of time partitioning is that at any time the state of the system processor, and the precise instruction executing at any given moment in time, can be known and predicted. Therefore in such an environment the Worst Case Execution Time (WCET) of any deterministic task can be accurately measured.
However, as processor technology has evolved to incorporate superscalar architectures, branch prediction, caching and other features, instruction timing has become impossible to perform with any certainty. Contemporary avionics interpretations of determinism refer to “bounded determinism”, which emphasizes establishing an upper bound on non-deterministic effects inherent in today's modern processors. These non-deterministic effects typically have one of three causes: asynchronous events, unbounded inputs, or contention for resources. Asynchronous events (e.g., interrupts or system messages), may be mitigated by avoiding or disabling interrupts, or through intermediate buffering via I/O or network offload processor. Unbounded inputs (e.g., a “storm” of interrupts or flood of Ethernet packets) may be mitigated by leaky buckets or other flow control mechanisms. Contention for resources (e.g., sharing of cache, RAM, busses) may be mitigated by limiting its impact (e.g., cache way locking) or by accounting for contention in WCET analysis.
The upper bound of an application then informs the scheduling of deadlines and the WCET analysis of the application. In order to improve determinism in an avionics environment, tradeoffs are generally made. For example, polling-based I/O may be used to minimize or eliminate sources of interrupts in an avionics system, sacrificing a portion of the CPU to achieve bounded determinism.
In an ARINC 653 environment, for example, scheduling of tasks (ex.—threads, processes, applications) is done via a cyclic fixed-time scheduler which provides each partition with a fixed amount of time per a predetermined schedule. To ensure the viability of a schedule, scheduling analysis may be performed (e.g., via Rate Monotonic Analysis or other equivalent scheduling algorithms). Scheduling fixed time partitions (ex.—time slices) is generally viewed as an acceptable sacrifice for avionics applications, which can be inherently cyclic in nature as they respond with fixed frequency to changes in airspeed, altitude, and the environment. The workload is discrete and deterministic (a known set of inputs and a well-defined sense of schedule) and thus somewhat predictable. ARINC 653 works in this context because it guarantees a fixed amount of processing to solve a fixed problem.
In both commercial and avionics applications, there is an increased need for soft real-time applications (e.g., video processing, map generation, terrain and obstacle recognition) that require a minimum level of processing but may yield an increased quality result given additional processing beyond the minimum level. For example, an obstacle avoidance process may detect the presence of an obstacle and roughly estimate its bounds or dimensions for display. With increased processing, however, it may be possible to characterize the obstacle as a wire, a tower, or a building, or to refine its bounds and produce a higher quality result for the pilot to interpret.
Because of the increased need for such soft real-time applications, scheduling priorities have shifted from requiring a fixed amount of scheduling to mobilizing all available scheduling not used by critical tasks and processes. At the same time, however, tasks must be managed so they do not consume an unbounded amount of processor time or resources and erode the foundation of ARINC 653 partitioning. It may therefore be desirable to guarantee a fixed amount of processing to some tasks while marshalling unused processing for soft real-time tasks, all while preserving time, space and resource partitioning.